﻿//#define MazeGenertorLoop // uncomment to run the generator in a loop
//#define DebugRandomMazeGeneration // uncomment me to watch the maze being built node-by-node
//#define UsePrims // uncomment me to use an alternate algorithm for maze generation

using System;
using System.Collections.Generic;
using System.Text;
using Towel.DataStructures;
using System.Threading.Tasks;

namespace Website.Games.Maze;

public class Maze
{
	public readonly BlazorConsole Console = new();
	public readonly BlazorConsole OperatingSystem;

	public Maze()
	{
		OperatingSystem = Console;
	}

	public async Task Run()
	{
		if (OperatingSystem.IsWindows())
		{
			Console.WindowHeight = 32;
		}
		const int rows = 8;
		const int columns = 20;
		static MazeClass.Tile[,] GenerateMaze() =>
#if UsePrims
			MazeClass.GeneratePrims(rows, columns);
#else
			MazeClass.Generate(rows, columns);
#endif
#if MazeGenertorLoop
		while (true)
		{
			MazeClass.Tile[,] maze = GenerateMaze();
			Console.Clear();
			Console.WriteLine(Maze.Render(maze));
			Console.WriteLine("Press Enter To Continue...");
			Console.ReadLine();
		}
#else
		Console.CursorVisible = true;
		MazeClass.Tile[,] maze = GenerateMaze();
		await Console.Clear();
		await Console.WriteLine(MazeClass.Render(maze));
		await Console.WriteLine();
		await Console.WriteLine("Maze");
		await Console.WriteLine("Solve the maze by using the arrow keys.");
		await Console.WriteLine("Press escape to quit.");
		int row = 0;
		int column = 0;
		while (row != rows - 1 || column != columns - 1)
		{
			await Console.SetCursorPosition(column * 3 + 1, row * 3 + 1);
			switch ((await Console.ReadKey(true)).Key)
			{
				case ConsoleKey.UpArrow:
					if (maze[row, column].HasFlag(MazeClass.Tile.Up))
						row--;
					break;
				case ConsoleKey.DownArrow:
					if (maze[row, column].HasFlag(MazeClass.Tile.Down))
						row++;
					break;
				case ConsoleKey.LeftArrow:
					if (maze[row, column].HasFlag(MazeClass.Tile.Left))
						column--;
					break;
				case ConsoleKey.RightArrow:
					if (maze[row, column].HasFlag(MazeClass.Tile.Right))
						column++;
					break;
				case ConsoleKey.Escape:
					await Console.Clear();
					await Console.Write("MMaze was closed.");
					await Console.Refresh();
					return;
			}
		}
		await Console.Clear();
		await Console.Write("You Win.");
		await Console.Refresh();
#endif
	}

	public static class MazeClass
	{
		[Flags]
		public enum Tile
		{
			Null = 0,
			Up = 1,
			Down = 2,
			Left = 4,
			Right = 8,
			Start = 16,
			End = 32,
		}

		#region Algorithm 1

		internal class Node
		{
			internal int Row;
			internal int Column;
			internal bool UpExplored;
			internal bool DownExplored;
			internal bool LeftExplored;
			internal bool RightExplored;
		}

		public static Tile[,] Generate(
			int rows, int columns,
			int? start_row = null, int? start_column = null,
			int? end_row = null, int? end_column = null)
		{
			// parameter defaults
			start_row ??= 0;
			start_column ??= 0;
			end_row ??= rows - 1;
			end_column ??= columns - 1;

			#region Exceptions
			if (rows <= 1)
				throw new ArgumentOutOfRangeException(nameof(rows));
			if (columns <= 1)
				throw new ArgumentOutOfRangeException(nameof(columns));
			if (start_row < 0 || rows < start_row)
				throw new ArgumentOutOfRangeException(nameof(start_row));
			if (end_row < 0 || rows < end_row || start_row == end_row)
				throw new ArgumentOutOfRangeException(nameof(end_row));
			if (start_column < 0 || columns < start_column)
				throw new ArgumentOutOfRangeException(nameof(start_column));
			if (end_column < 0 || columns < end_column || start_column == end_column)
				throw new ArgumentOutOfRangeException(nameof(end_column));
			#endregion

			Tile[,] maze = new Tile[rows, columns];
			var directionBuffer = new (int Row, int Column)[4];

			maze[start_row.Value, start_column.Value] = Tile.Start;
			maze[end_row.Value, end_column.Value] = Tile.End;

			// generate a valid path (so the maze is guaranteed to be solve-able)
			{
				var stack = new Stack<Node>();
				stack.Push(new Node()
				{
					Row = start_row.Value,
					Column = start_column.Value,
				});

				#region Optimizations

				// optimizations to prevent the algorithm from exploring unnecessary isolations
				// that will never reach the end of the maze. these currently depend on using the
				// default start/end locations, but they could be improved to help with custom
				// locations too. I am just lazy and didn't care enough to make a more general
				// purpose algorithm...

				bool DefaultLocations() =>
					start_row is 0 && start_column is 0 &&
					end_row == rows - 1 && end_column == columns - 1;
				bool UpOptimization(int column) => !(DefaultLocations() && column == columns - 1 || column is 0);
				bool LeftOptimization(int row) => !(DefaultLocations() && row == rows - 1 || row is 0);

				#endregion

				static bool NullOrEnd(Tile tile) => tile is Tile.Null || tile is Tile.End;

				bool MoveRandom()
				{
					Node node = stack.Peek();
					int i = 0;
					// populate possible moves
					if (node.Row != rows - 1 && NullOrEnd(maze[node.Row + 1, node.Column]) && !node.DownExplored)
						directionBuffer[i++] = (node.Row + 1, node.Column);
					if (node.Row != 0 && NullOrEnd(maze[node.Row - 1, node.Column]) && !node.UpExplored && UpOptimization(node.Column))
						directionBuffer[i++] = (node.Row - 1, node.Column);
					if (node.Column != 0 && NullOrEnd(maze[node.Row, node.Column - 1]) && !node.LeftExplored && LeftOptimization(node.Row))
						directionBuffer[i++] = (node.Row, node.Column - 1);
					if (node.Column != columns - 1 && NullOrEnd(maze[node.Row, node.Column + 1]) && !node.RightExplored)
						directionBuffer[i++] = (node.Row, node.Column + 1);
					// if no possibilities return false
					if (i is 0)
					{
						return false;
					}
					// get a random move from the possibilities
					var move = directionBuffer[Random.Shared.Next(0, i)];
					// mark the move as explored
					if (move.Row == node.Row + 1)
					{
						node.DownExplored = true;
						maze[node.Row, node.Column] |= Tile.Down;
						maze[move.Row, move.Column] |= Tile.Up;
					}
					if (move.Row == node.Row - 1)
					{
						node.UpExplored = true;
						maze[node.Row, node.Column] |= Tile.Up;
						maze[move.Row, move.Column] |= Tile.Down;
					}
					if (move.Column == node.Column - 1)
					{
						node.LeftExplored = true;
						maze[node.Row, node.Column] |= Tile.Left;
						maze[move.Row, move.Column] |= Tile.Right;
					}
					if (move.Column == node.Column + 1)
					{
						node.RightExplored = true;
						maze[node.Row, node.Column] |= Tile.Right;
						maze[move.Row, move.Column] |= Tile.Left;
					}
					stack.Push(new Node()
					{
						Row = move.Row,
						Column = move.Column,
					});
					// return the move
					return true;
				}

				while (stack.Peek().Row != end_row || stack.Peek().Column != end_column)
				{
					if (!MoveRandom())
					{
						Node move = stack.Pop();
						maze[move.Row, move.Column] = Tile.Null;
						Node parent = stack.Peek();
						if (move.Row == parent.Row - 1) maze[parent.Row, parent.Column] &= ~Tile.Up;
						if (move.Row == parent.Row + 1) maze[parent.Row, parent.Column] &= ~Tile.Down;
						if (move.Column == parent.Column + 1) maze[parent.Row, parent.Column] &= ~Tile.Right;
						if (move.Column == parent.Column - 1) maze[parent.Row, parent.Column] &= ~Tile.Left;
					}

#if DebugRandomMazeGeneration
				Console.Clear();
				Console.WriteLine(Render(maze));
				Console.WriteLine("Press Enter To Continue...");
				Console.ReadLine();
#endif
				}
			}

			// Generate invalid paths (to fill in the rest of the maze)
			{
				var stack = new Stack<Node>();
				var invalidPath = new HashSet<(int Row, int Column)>();
				var previousMoves = new Stack<Tile>();

				int CountNulls()
				{
					int count = 0;
					for (int row = 0; row < rows; row++)
						for (int column = 0; column < columns; column++)
							if (maze[row, column] is Tile.Null)
								count++;
					return count;
				}

				(int Row, int Column)? GetRandomNull(int? nullCount = null)
				{
					int nullCountInt = nullCount ?? CountNulls();
					// if no Tile.Null's, return null
					if (nullCountInt <= 0) return null;
					// nulls exist, get a random one
					int index = Random.Shared.Next(0, nullCountInt + 1);
					(int, int) @null = default;
					for (int row = 0; row < rows && index > 0; row++)
						for (int column = 0; column < columns && index > 0; column++)
							if (maze[row, column] is Tile.Null && --index is 0)
								@null = (row, column);
					return @null;
				}

				bool MoveRandom()
				{
					Node node = stack.Peek();
					int i = 0;
					if (node.Row != rows - 1 && !invalidPath.Contains((node.Row + 1, node.Column)) && !node.DownExplored)
						directionBuffer[i++] = (node.Row + 1, node.Column);
					if (node.Row != 0 && !invalidPath.Contains((node.Row - 1, node.Column)) && !node.UpExplored)
						directionBuffer[i++] = (node.Row - 1, node.Column);
					if (node.Column != 0 && !invalidPath.Contains((node.Row, node.Column - 1)) && !node.LeftExplored)
						directionBuffer[i++] = (node.Row, node.Column - 1);
					if (node.Column != columns - 1 && !invalidPath.Contains((node.Row, node.Column + 1)) && !node.RightExplored)
						directionBuffer[i++] = (node.Row, node.Column + 1);
					if (i is 0)
						return false;
					var move = directionBuffer[Random.Shared.Next(0, i)];
					if (move.Row == node.Row + 1)
					{
						node.DownExplored = true;
						maze[node.Row, node.Column] |= Tile.Down;
						maze[move.Row, move.Column] |= Tile.Up;
						previousMoves.Push(Tile.Up);
					}
					if (move.Row == node.Row - 1)
					{
						node.UpExplored = true;
						maze[node.Row, node.Column] |= Tile.Up;
						maze[move.Row, move.Column] |= Tile.Down;
						previousMoves.Push(Tile.Down);
					}
					if (move.Column == node.Column - 1)
					{
						node.LeftExplored = true;
						maze[node.Row, node.Column] |= Tile.Left;
						maze[move.Row, move.Column] |= Tile.Right;
						previousMoves.Push(Tile.Right);
					}
					if (move.Column == node.Column + 1)
					{
						node.RightExplored = true;
						maze[node.Row, node.Column] |= Tile.Right;
						maze[move.Row, move.Column] |= Tile.Left;
						previousMoves.Push(Tile.Left);
					}
					stack.Push(new Node()
					{
						Row = move.Row,
						Column = move.Column,
					});
					invalidPath.Add((node.Row, node.Column));
					return true;
				}

				(int Row, int Column)? nullStart;
				while ((nullStart = GetRandomNull()).HasValue)
				{
					stack.Clear();
					invalidPath.Clear();
					stack.Push(new Node()
					{
						Row = nullStart.Value.Row,
						Column = nullStart.Value.Column,
					});
					invalidPath.Add((nullStart.Value.Row, nullStart.Value.Column));
					previousMoves.Clear();
					previousMoves.Push(Tile.Null);
					while (maze[stack.Peek().Row, stack.Peek().Column] == previousMoves.Peek())
					{
						if (!MoveRandom())
						{
							Node move = stack.Pop();
							Node parent = stack.Peek();
							previousMoves.Pop();
							if (move.Row == parent.Row - 1)
							{
								maze[move.Row, move.Column] &= ~Tile.Down;
								maze[parent.Row, parent.Column] &= ~Tile.Up;
							}
							if (move.Row == parent.Row + 1)
							{
								maze[move.Row, move.Column] &= ~Tile.Up;
								maze[parent.Row, parent.Column] &= ~Tile.Down;
							}
							if (move.Column == parent.Column + 1)
							{
								maze[move.Row, move.Column] &= ~Tile.Left;
								maze[parent.Row, parent.Column] &= ~Tile.Right;
							}
							if (move.Column == parent.Column - 1)
							{
								maze[move.Row, move.Column] &= ~Tile.Right;
								maze[parent.Row, parent.Column] &= ~Tile.Left;
							}
						}

#if DebugRandomMazeGeneration
					Console.Clear();
					Console.WriteLine(Render(maze));
					Console.WriteLine("Press Enter To Continue...");
					Console.ReadLine();
#endif
					}
				}
			}

			return maze;
		}

		#endregion

		#region Algorithm 2 (Prims)

		public class Graph
		{
			public class Node
			{
				public int OwnIndex { get; }
				public List<int> Connections { get; }
				public List<double> Costs { get; }

				public void Add(int other, double cost)
				{
					Connections.Add(other);
					Costs.Add(cost);
				}

				public Node(int ownIndex)
				{
					OwnIndex = ownIndex;
					Connections = new List<int>();
					Costs = new List<double>();
				}
			}

			public Node[] Nodes { get; }

			public Graph(Node[] nodes)
			{
				Nodes = nodes ?? throw new ArgumentNullException(nameof(nodes));
			}

			public static MazeClass.Tile[,] ConvertToGrid(Graph graph, int rows, int columns, Func<int, int, int> index, int start_row, int start_column, int end_row, int end_column)
			{
				var tiles = new MazeClass.Tile[rows, columns];

				foreach (var node in graph.Nodes)
				{
					if (node == null)
						continue;

					(int, int) Unpack(int i) => (i % rows, i / rows);

					var (row, col) = Unpack(node.OwnIndex);

					// directional
					if (node.Connections.Contains(index(row - 1, col)))
					{
						tiles[row, col] |= MazeClass.Tile.Up;
						tiles[row - 1, col] |= MazeClass.Tile.Down;
					}
					if (node.Connections.Contains(index(row + 1, col)))
					{
						tiles[row, col] |= MazeClass.Tile.Down;
						tiles[row + 1, col] |= MazeClass.Tile.Up;
					}
					if (node.Connections.Contains(index(row, col - 1)))
					{
						tiles[row, col] |= MazeClass.Tile.Left;
						tiles[row, col - 1] |= MazeClass.Tile.Right;
					}
					if (node.Connections.Contains(index(row, col + 1)))
					{
						tiles[row, col] |= MazeClass.Tile.Right;
						tiles[row, col + 1] |= MazeClass.Tile.Left;
					}

					// start/end
					if (row == start_row && col == start_column)
					{
						tiles[row, col] |= MazeClass.Tile.Start;
					}
					if (row == end_row && col == end_column)
					{
						tiles[row, col] |= MazeClass.Tile.End;
					}
				}
				return tiles;
			}
		}

		public static Tile[,] GeneratePrims(
			int rows, int columns,
			int? start_row = null, int? start_column = null,
			int? end_row = null, int? end_column = null)
		{
			start_row ??= 0;
			start_column ??= 0;
			end_row ??= rows - 1;
			end_column ??= columns - 1;

			var grid = new Graph.Node[rows * columns];

			int Index(int row, int col) => row + rows * col;

			for (int row = 0; row < rows; row++)
			{
				for (int col = 0; col < columns; col++)
				{
					var n = new Graph.Node(Index(row, col));
					if (row + 1 < rows)
					{
						n.Add(Index(row + 1, col), Random.Shared.NextDouble());
					}
					if (row - 1 >= 0)
					{
						n.Add(Index(row - 1, col), Random.Shared.NextDouble());
					}
					if (col + 1 < columns)
					{
						n.Add(Index(row, col + 1), Random.Shared.NextDouble());
					}
					if (col - 1 >= 0)
					{
						n.Add(Index(row, col - 1), Random.Shared.NextDouble());
					}
					grid[Index(row, col)] = n;
				}
			}

			var graph = new Graph(grid);

#if DebugRandomMazeGeneration
		Console.Clear();
		Console.WriteLine(Maze.Render(Graph.ConvertToGrid(graph, rows, columns, Index, start_row.Value, start_column.Value, end_row.Value, end_column.Value)));
		Console.WriteLine("Press Enter To Continue...");
		Console.ReadLine();
		var res = SimplePrims(graph, rows, columns, Index, start_row.Value, start_column.Value, end_row.Value, end_column.Value);
#else
			var res = SimplePrims(graph);
#endif

			return Graph.ConvertToGrid(res, rows, columns, Index, start_row.Value, start_column.Value, end_row.Value, end_column.Value);
		}

		private readonly struct TwoWayConnection : IComparable<TwoWayConnection>
		{
			public readonly int IndexA;
			public readonly int IndexB;
			public readonly double Cost;

			public TwoWayConnection(int indexA, int indexB, double cost)
			{
				IndexA = indexA;
				IndexB = indexB;
				Cost = cost;
			}

			public int CompareTo(TwoWayConnection other) => other.Cost.CompareTo(Cost); // inversed because of how the heap works
		}

		public static Graph SimplePrims(Graph graph
#if DebugRandomMazeGeneration
		, int rows, int columns, Func<int, int, int> index, int start_row, int start_column, int end_row, int end_column
#endif
		)
		{
			var newGraph = new Graph(new Graph.Node[graph.Nodes.Length]);
			var nodes = graph.Nodes;
			var current = nodes[0];
			newGraph.Nodes[0] = new Graph.Node(0);

			var heap = HeapArray.New<TwoWayConnection>();

			while (true)
			{
				for (int i = 0; i < current.Connections.Count; i++)
				{
					heap.Enqueue(new TwoWayConnection(current.OwnIndex, current.Connections[i], current.Costs[i]));
				}

				TwoWayConnection c;
				do
				{
					if (heap.Count is 0)
					{
						return newGraph;
					}
					c = heap.Dequeue();
				}
				while (newGraph.Nodes[c.IndexB] != null);

				newGraph.Nodes[c.IndexA].Add(c.IndexB, c.Cost);

				newGraph.Nodes[c.IndexB] = new Graph.Node(c.IndexB);
				current = graph.Nodes[c.IndexB];
				newGraph.Nodes[c.IndexB].Add(c.IndexA, c.Cost);

#if DebugRandomMazeGeneration
			Console.Clear();
			Console.WriteLine(Maze.Render(Graph.ConvertToGrid(newGraph, rows, columns, index, start_row, start_column, end_row, end_column)));
			Console.WriteLine("Press Enter To Continue...");
			Console.ReadLine();
#endif
			}
		}

		#endregion

		public static string Render(Tile[,] maze)
		{
			static char Center(Tile tile) =>
				tile.HasFlag(Tile.Start) ? 'S' :
				tile.HasFlag(Tile.End) ? 'E' :
				/* default */ ' ';

			static char Side(Tile tile, Tile flag) =>
				tile.HasFlag(flag) ? ' ' : '█';

			static char[,] RenderTile(Tile tile) => new char[,]
			{
			{ '█', Side(tile, Tile.Up), '█' },
			{ Side(tile, Tile.Left), Center(tile), Side(tile, Tile.Right) },
			{ '█', Side(tile, Tile.Down), '█' },
			};
			int rows = maze.GetLength(0);
			int columns = maze.GetLength(1);
			char[,][,] rendered = new char[rows, columns][,];
			for (int row = 0; row < rows; row++)
			{
				for (int column = 0; column < columns; column++)
				{
					rendered[row, column] = RenderTile(maze[row, column]);
				}
			}
			int rowsX3 = rows * 3;
			int columnsX3 = columns * 3;
			StringBuilder stringBuilder = new();
			for (int row = 0; row < rowsX3; row++)
			{
				for (int column = 0; column < columnsX3; column++)
				{
					int tileRow = row / 3;
					int tileColumn = column / 3;
					int renderRow = row % 3;
					int renderColumn = column % 3;
					stringBuilder.Append(rendered[tileRow, tileColumn][renderRow, renderColumn]);
				}
				stringBuilder.AppendLine();
			}
			string render = stringBuilder.ToString();
			return render;
		}
	}
}
